The binomial coefficient 10C3 = 120. 120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5, and 2 + 2 + 2 + 3 + 5 = 14. So the sum of the terms in the prime factorisation of 10C3 is 14.
Find the sum of the terms in the prime factorisation of 20000000C15000000.
In [1]:
def digitsum(n, p):
"""Sum of digits of n in base p"""
s = 0
while n:
s += n % p
n //= p
return s
def binom(n, k, p):
"""Exponent of p in the prime factorization of (n choose k)."""
return (digitsum(k, p) + digitsum(n - k, p) - digitsum(n, p)) // (p - 1)
In [2]:
from primesieve import primes
def sum_of_prime_factors_binom(n, k):
return sum(p * binom(n, k, p) for p in primes(n))
In [3]:
print(sum_of_prime_factors_binom(20000000, 15000000))
In [ ]: